package baseclass.a_sort.bucketSort;


import baseclass.a_sort.ArraysTool;

import java.util.Arrays;

/**
 * @date 2020/2/26 23:06
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {3, 1, -1};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bucketSort(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        //get min and max
        int min = arr[0];
        int max = arr[0];
        for (int e : arr) {
            min = Math.min(min, e);
            max = Math.max(max, e);
        }
        //譬如min = -1, max = 3
        int[] bucket = new int[max - min + 1];
        //把arr装入bucket
        for (int e : arr) {
            //按照min归一化，bucket的索引就是arr中的元素值，bucket的值就是元素对应个数
            bucket[e - min]++;
        }
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            //譬如bucket[0] = 10,代表有10个  0-min
            while (bucket[i]-- > 0) {
                arr[index++] = i + min;
            }
        }
    }
}
